package chapter5_stack_and_linked;


import java.util.LinkedList;

/**
 * @Author yuh
 * @Date Created in 上午7:24 2018/4/11
 * @Description 链表往上面加元素不能动head 遍历直接动head next也可往前指
 */
public class ReverseLinked {

    static class ListNode {
        int e;
        ListNode next;

        public ListNode(int e) {
            this.e = e;
        }
    }


    static ListNode createLink(int[] arr) {
        ListNode node = new ListNode(arr[0]);
        ListNode cur = node;
        for (int i = 1; i < arr.length; i++) {
            cur.next = new ListNode(arr[i]);
            cur = cur.next;
        }
        return node;
    }

    static ListNode reverseLink(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode next;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    static ListNode reverseLink1(ListNode head) {
        ListNode pre = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    static void printLink(ListNode head) {
        System.out.print(head.e + "->");
        while (head.next != null) {
            ListNode next = head.next;
            System.out.print(next.e + "->");
            head = head.next;
        }
        System.out.println("NUll");
    }

    /**
     * 删除指定全部元素 返回删除后的链表 硬删法
     *
     * @param node
     * @param val
     * @return
     */
    static ListNode removeNode(ListNode head, int val) {
        //如果头为null
        if (head == null) {
            return null;
        }
        //如果头就是 那么就直接换头
        while (head.e == val) {
            head = head.next;
        }

        //临时复制一个节点 用于往后走 因为head还要返回
        ListNode cur = head;

        while (cur != null && cur.next != null) {
            ListNode next = cur.next;
            if (next.e == val) {
                //下一个元素是 就指向下一个元素的下一个元素
                cur.next = next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }

    /**
     * 采用虚拟节点法 优化删除一个元素的问题
     * 单项链表删除节点时 就是在当前节点看下一个节点是否符合规则 如果符合的话就指向下一个节点的下一个节点
     * 第一种情况是 直接考虑头就是空的情况 全都在头的情况
     * 第二种情况就是实用虚拟节点走正常逻辑
     *
     * @param head
     * @param val
     * @return
     */
    static ListNode removeNode1(ListNode head, int val) {
        ListNode listNode = new ListNode(0);
        listNode.next = head;
        ListNode cur = listNode;
        while (cur.next != null) {
            ListNode next = cur.next;
            if (next.e == val) {
                cur.next = next.next;
            } else {
                cur = cur.next;
            }
        }
        return listNode.next;
    }

    /**
     * 交换成对的元素 进来一个链表新建指针操作 不操作原有指针
     * pre: 1->2->3->4->null
     * post: 2->1->4->3->null
     *
     * @param head
     * @return
     */
    static ListNode exchagePair(ListNode head) {
        //创造一个虚拟的节点
        ListNode vNode = new ListNode(0);
        vNode.next = head;
        //判断是否还有交换的余地
        ListNode p = vNode;
        while (p.next != null && p.next.next != null) {
            ListNode node1 = p.next;
            ListNode node2 = node1.next;
            //可能为空
            ListNode post = node2.next;
            node2.next = node1;
            node1.next = post;
            p.next = node2;
            p = node1;
        }
        return vNode.next;
    }


    /**
     * 删除给定的节点
     *
     * @param node
     */
    static void removeNode(ListNode node) {
        if (node == null) {
            return;
        }

        if (node.next == null) {
            node = null;
        }

        node.e = node.next.e;
        node.next = node.next.next;
    }

    /**
     * 删除从尾部非空元素计算的第n个元素 两重循环法
     *
     * @param n
     * @return
     */
    static ListNode removeNthOfEnd(ListNode head, int n) {
        int all = -1;
        ListNode vNode = new ListNode(0);
        vNode.next = head;
        ListNode cur = vNode;

        //一共有几个元素
        while (cur != null) {
            all++;
            cur = cur.next;
        }
        cur = vNode;

        //得到要删除元素的前一个元素
        int index = all - n - 1;
        for (int i = 0; i <= index; i++) {
            cur = cur.next;
            if (i == index) {
                cur.next = cur.next.next;
                break;
            }
        }

        //System.out.println(all);
        return vNode.next;
    }


    /**
     * 删除从尾部非空元素计算的第n个元素 一重循环法
     *
     * @param n
     * @return
     */
    static ListNode removeNthOfEnd1(ListNode head, int n) {
        //建立一个虚拟节点和两个虚拟指针
        ListNode vNode = new ListNode(0);
        vNode.next = head;
        ListNode p = vNode;
        ListNode q = vNode;

        //首先让pq拉开距离
        for (int i = 0; i < n + 1; i++) {
            q = q.next;
        }

        //然后让q走到最后 p所在的位置就是要删除的元素的前一个元素
        while (q != null) {
            q = q.next;
            p = p.next;
        }

        p.next = p.next.next;
        return vNode.next;
    }


    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 5};
        ListNode head = createLink(arr);
        printLink(head);
        // ListNode listNode = reverseLink1(head);
        //ListNode listNode = removeNode(head, 5);
        //ListNode listNode = exchagePair(head);
        // ListNode listNode1 = reverseLink1(listNode);
        //removeNode(head.next.next);
        //printLink(head);
        printLink(removeNthOfEnd1(head, 2));

    }
}
